package org.example.tree;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author liyishan
 * @date 2023/9/25 09:48
 * @apiNote
 */

public class Test00106BuildTree {

    public TreeNode buildTree1(int[] inorder, int[] postorder) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i],i);
        }
        return  dfs(0,inorder.length-1,0,postorder.length-1,postorder,map);
    }

    public static TreeNode dfs(int is, int ie, int ps, int pe, int[] postorder, Map<Integer,Integer> map){
        if(ie < is || pe <ps){
            return null;
        }
        int root =  postorder[pe];
        int ri = map.get(root);
        TreeNode node = new TreeNode(root);
        node.left = dfs(is,ri-1,ps,ps+ri-is-1,postorder,map);
        node.right = dfs(ri+1,ie,ps+ri-is,pe-1,postorder,map);
        return node;
    }



    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(postorder == null || postorder.length == 0){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        Deque<TreeNode> stack = new LinkedList<>();
        stack.push(root);
        int inorderIndex = inorder.length-1;
        for(int i = postorder.length - 2;i>=0;i--){
            int postorderVal = postorder[i];
            TreeNode node = stack.peek();
            if(node.val != inorder[inorderIndex]){
                node.right = new TreeNode(postorderVal);
                stack.push(node.right);
            }else{
                while(!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]){
                    node = stack.pop();
                    inorderIndex--;
                }
                node.left = new TreeNode(postorderVal);
                stack.push(node.left);
            }
        }
        return root;
    }
}
